// Copyright (c) [Year] [name of copyright holder]
// [Software Name] is licensed under Mulan PSL v2.
// You can use this software according to the terms and conditions of the Mulan PSL v2. 
// You may obtain a copy of Mulan PSL v2 at:
//          http://license.coscl.org.cn/MulanPSL2 
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.  
// See the Mulan PSL v2 for more details.

/*!
 * \autor captainpeng
 * \date 2019-2-28
 * \update 2019-3-11
 * \version 1.0
 * \copyright
 */

#ifndef MY_LIST_HPP
#define MY_LIST_HPP

#include"mystd.hpp"
#include"stack.hpp"

namespace my{

    template<typename T>
    struct listNode{
        using elementType = T;

        elementType mValue;
        listNode * mNext;
    };

    template<typename T>
    class list{
    public:
        using nodeType = listNode<info_type_t<T>>;
        using nodePtr = nodeType *;
        using elementType = typename nodeType::elementType;

        using memType = my::memory;

    private:
        nodePtr mHead;

        static nodePtr * FindEnd(nodePtr * node){
            while(*node != nullptr)
                node = &((*node)->mNext);
            return node;
        }

        static nodePtr * FindElement(nodePtr * node, const elementType & val){
            while((*node)->mValue != val)
                node = &((*node)->mNext);
            return node;
        }

        static nodePtr * FindPos(nodePtr * node, const int pos){
            for(int i = 0; i < pos && (*node) != nullptr; ++i)
                node = &((*node)->mNext);
            return node;
        }

        // 分配内存块并插入当前的位置
        // 函数执行后，若无异常，则 *p 则是当前新分配的 node
        static void AllocAndInsert(nodePtr * p){
            nodePtr tmp = memType::calloc<nodeType>(1);
            tmp->mNext = *p;
            *p = tmp;
        }

        // 删掉 node 并释放内存块
        inline void EraseAndFree(nodePtr * p){
            if(*p != nullptr){
                nodePtr tmp = *p;
                *p = tmp->mNext;
                memType::free(tmp);
            }
        }

    public:
        list():mHead(nullptr){}

        list(list && rhs){
            mHead = rhs.mHead;
            rhs.mHead = nullptr;
        }

        list & operator=(list && rhs){
            free();
            mHead = rhs.mHead;
            rhs.mHead = nullptr;
        }

        ~list(){
            free();
        }

        void insert(const elementType & val){
            AllocAndInsert(&mHead);
            mHead->mValue = val;
        }

        void insert(elementType && val){
            AllocAndInsert(&mHead);
            mHead->mValue = std::move(val);
        }
	
        void insert(const elementType & val,const int pos){
            nodePtr * tmp = FindPos(&mHead, pos);
            AllocAndInsert(tmp);
            (*tmp)->mValue = val;
        }

        void push(const elementType & val){
            nodePtr * tmp = FindEnd(&mHead);
            AllocAndInsert(tmp);
            (*tmp)->mValue = val;
        }

        void push(elementType && val){
            nodePtr * tmp = FindEnd(&mHead);
            AllocAndInsert(tmp);
            (*tmp)->mValue = std::move(val);
        }

        bool exist(nodePtr p){
            nodePtr tmp = mHead;
            while(tmp != nullptr){
                if(tmp == p)
                    return true;
                tmp = tmp->mNext;
            }
            return false;
        }
	
        elementType * find(const elementType & et){
            nodePtr * node = FindElement(&mHead, et);
            return (*node == nullptr)? nullptr:&(*node)->mValue;
        }

        elementType * findByPos(int pos){
            nodePtr * node = FindPos(&mHead, pos);
            return (*node == nullptr)? nullptr:&(*node)->mValue;
        }

        void erase(const elementType & val){
            EraseAndFree(FindElement(val));
        }

        void free(){
            nodePtr head = mHead;
            nodePtr cur = mHead;
            while(cur != nullptr){
                head = head->mNext;

                cur->mNext = nullptr;
                memType::free(cur);
                cur = head;
            }

            mHead = nullptr;
        }

        template<typename CALL, typename ... ARGS>
        void each(const CALL & call, ARGS && ... args){
            nodePtr tmp = mHead;
            while(tmp != nullptr){
                if(!call(tmp->mValue, std::forward<ARGS>(args) ...))
                    return ;
            }
        }

        void show(std::ostream & os = std::cout) const {
            nodePtr tmp = mHead;
            os<<"{";
            while(tmp != nullptr){
                os<<tmp->mValue;
                if(tmp->mNext != nullptr)
                    os<<',';
                tmp=tmp->mNext;
            }
            os<<"}";
        }
    };

    template<typename T>
    std::ostream & operator<<(std::ostream & os,const list<T> & l){
        l.show(os);
        return os;
    }
}

#endif
